2022. Convert 1D Array Into 2D Array

tags: Easy、Array

You are given a 0-indexed 1-dimensional (1D) integer array original, and two integers, m and n. You are tasked with creating a 2-dimensional (2D) array with m rows and n columns using all the elements from original.
The elements from indices 0 to n - 1 (inclusive) of original should form the first row of the constructed 2D array, the elements from indices n to 2 * n - 1 (inclusive) should form the second row of the constructed 2D array, and so on.
Return an m x n 2D array constructed according to the above procedure, or an empty 2D array if it is impossible.

解法:

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** construct2DArray(int* original, int originalSize, int m, int n, int* returnSize, int** returnColumnSizes) {
    *returnSize = m;

    //第一道檢測
    if (originalSize != (m * n)) {
        *returnSize = 0;
        **returnColumnSizes = NULL;
        return NULL;
    }

    //array分配記憶體
    int** array = (int**)malloc(m * sizeof(int*));
    // if (array == NULL) {
    //     return NULL; // Check for malloc failure
    // }
    

    //分配記憶體給returnColumnSizes
    *returnColumnSizes = (int*)malloc(m * sizeof(int));
    // if (*returnColumnSizes == NULL) {
    //     free(array);
    //     return NULL;
    // }
    for (int i = 0; i < m; i++) {
        (*returnColumnSizes)[i] = n;
    }

    for (int i = 0; i < m; i++) {
        array[i] = (int*)malloc(n * sizeof(int));
        // if (array[i] == NULL) {
        //     for (int k = 0; k < i; k++) {
        //         free(array[k]);
        //     }
        //     free(array);
        //     free(*returnColumnSizes);
        //     return NULL;
        // }
    }

    //複製值到正確的位置中 [1,2,3,4,5,6] -> [[1,2], [3,4], [5,6]] m=3, n=2
    for (int i = 0; i < m; i++) {              // 0  , 1  ,2
        for (int j = 0; j < n; j++) { 
            array[i][j] = original[i * n + j]; // 0,1 |2,3|4,5
        }
    }
    return array;
}

965. Univalued Binary Tree

tags: Easy、Tree

A binary tree is uni-valued if every node in the tree has the same value.
Given the root of a binary tree, return true if the given tree is uni-valued, or false otherwise.

解法:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool checkval (struct TreeNode* node, int val) {
    if (node == NULL) {
        return true;
    }
    
    return ((node->val == val) && checkval(node->left, val) && checkval(node->right, val));
}

bool isUnivalTree(struct TreeNode* root) {
    if (root == NULL) {
        return true;
    }
    return checkval(root, root->val);
}

94. Binary Tree Inorder Traversal

tags: Easy、Tree

Given the root of a binary tree, return the inorder traversal of its nodes' values.

解法1: 遞迴

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
// 計算節點數量 --> 也可以不計算節點數量，直接以100為上限(from 題目)
int countNode(struct TreeNode* node) {
    if (!node) {
        return 0;
    }
    return (1 + countNode(node->left) + countNode(node->right));
}

// 遞迴做中序訪問
void inordertrace(struct TreeNode* node, int* array, int* index) {
    if (!node) {
        return ;
    }

    inordertrace(node->left, array, index);
    array[(*index)++] = node->val;
    inordertrace(node->right, array, index); 
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    //計算節點數量得到正確的returnSize值
    int count = countNode(root);
    int* array = (int*)malloc(count * sizeof(int));

    //藉由遞迴來處理中序，並將訪問到的node放入array中
    int index = 0;
    inordertrace(root, array, &index);
    *returnSize = index;
    return array;
}

解法2: 迭代

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    struct TreeNode* stack[100];
    int top = -1;
    int* array = (int*)malloc(100 * sizeof(int));
    int index = 0;

    struct TreeNode* curr = root;

    while (curr != NULL || top != -1) {
        while (curr != NULL) {
            stack[++top] = curr;
            curr = curr->left;
        }
        curr = stack[top--];
        array[index++] = curr->val;
        curr = curr->right;
    }
    *returnSize = index;
    return array;
}